A Hybrid Evolutionary Algorithm Based on Solution Merging for the Longest Arc-Preserving Common Subsequence Problem

摘要

The longest arc-preserving common subsequence problem is an NP-hardcombinatorial optimization problem from the field of computational biology.This problem finds applications, in particular, in the comparison ofarc-annotated Ribonucleic acid (RNA) sequences. In this work we propose asimple, hybrid evolutionary algorithm to tackle this problem. The mostimportant feature of this algorithm concerns a crossover operator based onsolution merging. In solution merging, two or more solutions to the problem aremerged, and an exact technique is used to find the best solution within thisunion. It is experimentally shown that the proposed algorithm outperforms aheuristic from the literature.